/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package algoritmosprobab;

/**
 *
 * @author nathamg
 */

import java.math.BigInteger;
import java.util.Random;

public class MillerRabin {
    
    private int [] s_t;
    
    public MillerRabin()
    {
        s_t=new int [2];
    }
    
    public boolean test_primo(int n, int n_intentos)
    {
        boolean resp=true;
        int intentos=0;
        
        while(resp==true && intentos<n_intentos)
        {
            resp=millerRabin(n);
            //System.out.println(n+" respuesta "+intentos+" ="+resp);
            intentos++;
            
        }
        
        return resp;
    }
    
    public int nextPrimo(int min)
    {
        int primoResp;
        int primoTmp=min;
        boolean test=false;
        
        if(min%2==0)
        {
            primoTmp++;
        }
        
        else 
        {
            primoTmp+=2;
        }
        
        while(test!=true)
        {
            //System.out.println("probando: "+primoTmp);
            test=test_primo(primoTmp,5);
            //System.out.println("probado: "+primoTmp+" resultado "+test);
            primoTmp+=2;
        }
        
        primoResp=primoTmp-2;
        return primoResp;
    }
    
    public boolean millerRabin(int n)
    {
        boolean esPrimo=true;
        
        if(n==2) 
        {
            //System.out.println("soy 2");
            return true;
        }
        
        else if((n%2)==0&&(n!=2))
        {
            //System.out.println("soy par");
            return false;
        }
        
        else
        {   
            //TODO:cambiar a implementacion propia y no generar ceros
            Random genAleat=new Random();
 
            determinarValores(n-1);
            BigInteger a=BigInteger.valueOf(genAleat.nextInt(n)+1);
            //System.out.println("valor de a: "+a);
            //System.out.println("valor s: "+s_t[0]);
            //System.out.println("valor t: "+s_t[1]);
            
            BigInteger op3=a.modPow(BigInteger.valueOf(s_t[0]), BigInteger.valueOf(n));

            //System.out.println("valor de op3: "+op3);
            
            if(op3.equals(BigInteger.valueOf(1)))
            {
                return true;
            }
            
            else
            {
                int i=0;
                
                while(i<s_t[1])
                {
                    //System.out.println("valor i: "+i);
                    BigInteger opTmp=BigInteger.valueOf((int)(Math.pow(2, i))*s_t[0]);
                    //System.out.println("valor opTmp: "+opTmp);
                    BigInteger op2=a.modPow(opTmp,BigInteger.valueOf(n));
                    //System.out.println("valor op2: "+op2);
                            
                    if(op2.equals(BigInteger.valueOf(n-1)))
                    {
                        return true;
                    }
                    
                    i++;
                }
                
                return false;
            }
        }
    }
    
    private void determinarValores(int n)
    {
        int sTmp,t_tmp;
     
        sTmp=n;
        t_tmp=0;
        
        while(sTmp%2==0)
        {
            sTmp/=2;
            t_tmp++;
        }
          
        s_t[0]=sTmp;
        s_t[1]=t_tmp;
    }  
}
